package top

/**
 * @description: 127. Word Ladder 中等
	A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words
	beginWord -> s1 -> s2 -> ... -> sk such that:

	Every adjacent pair of words differs by a single letter.
	Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
	sk == endWord
	Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest
	transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
 * @return: 最短路径长度
 * @author: kami
 * @关键词：BFS广度优先遍历
 * @date: 2021/7/11 21:55
*/
func ladderLength(beginWord string, endWord string, wordList []string) int {
	var wordSet = make(map[string]bool)
	for i := 0; i < len(wordList); i++ {
		wordSet[wordList[i]] = true
	}
	// 没有目标单词
	if !wordSet[endWord] {
		return 0
	}
	var path = []string{beginWord}
	var level = 1
	for len(path) > 0 {
		var size = len(path)
		var curLevelPath []string
		for i := 0; i < size; i++ {
			cur := path[i]
			if cur == endWord {
				return level
			}
			delete(wordSet, cur)
			for j := 0; j < len(cur); j++ {
				var tmp = []byte(cur)
				for k := 0; k < 26; k++ {
					tmp[j] = byte('a' + k)
					tmpStr := string(tmp)
					if wordSet[tmpStr] {
						curLevelPath = append(curLevelPath, tmpStr)
					}
				}
			}
		}
		level++
		path = curLevelPath
	}
	return 0
}

/*
1. Two Sum
*/
func twoSum(nums []int, target int) []int {
	// 期待值：下标
	expect := make(map[int]int, 0)
	size := len(nums)
	for i := 0; i < size; i++ {
		expectVal := target - nums[i]
		if idx, ok := expect[expectVal]; ok {
			return []int{idx, i}
		}
		expect[nums[i]] = i
	}
	return []int{}
}

// ListNode Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

/*
2. Add Two Numbers
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	carry, dummy := 0, new(ListNode)
	for node := dummy; l1 != nil || l2 != nil || carry > 0; node = node.Next {
		if l1 != nil {
			carry += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			carry += l2.Val
			l2 = l2.Next
		}
		node.Next = &ListNode{carry % 10, nil}
		carry /= 10
	}
	return dummy.Next
}
